A stack is a special type of singly linked list, where the elements are accessed, inserted, and removed only from only one end
One of its end will be closed. ปลายข้างล่างก็คือปิดไง เหมือน Lay Stack
LIFO (last-in-first-out) data structure.
A stack only allows operations on the top element, while an array allows direct access to any element.
Stack Operation
push insert an item to the stack → addFirst of list
pop delete an item from the stack removeFirst of list
peek get an item at the top of the stack first of list
Stack Applications
Reversing the order
Finding the radix base
Check palindrome
Evaluating the postfix notation
Evaluating the infix expression
Checking Palindrome
A palindrome is a sequence of characters whose forward and backward sequences are the same.
To check palindrome, generate the stack containing the forward sequence of letters and another stack containing the backward sequence of the letter
One-by-one pop and compare the elements in both stacks pair by pair. If all pairs are the same, it is a palindrome. If at least a pair doesn’t match, it is not a palindrome.
Postfix Expression
มี Stack เดียว!
Postfix expression is an expression that an operator follows its operands
Ex. 3 4 +
12 3 / 5 4 - 1 9 + + -
It is sometimes called reversed polish notation.
It is parenthesis free.
In computer science, postfix notation is often used in stack-based and concatenative programming languages.
Infix Expression
มี 2 Stacks → Operator กับ Operand
An infix expression or a regular expression is an expression that an operator comes between its operands
Ex. 3 + 4
12 / 3 – ( 5 – 4 ) + ( 1 + 9 )
It can come with parenthesis.
It calculates based upon the priority of operators as follows
