UoL CS Notes
Menu

Queues & Stacks - 2

COMP108 Lectures

Stacks

The following are the operations on stacks:

  • Push - Insert element tot he location 1 beyond top.
  • Pop - Delete element from the top.

The stack has one pointer that points to the top-most data in the stack.

  • Push
    • Increment top by 1 and save the data to S[top].
  • Pop
    • Retrieve data from S[top] and decrement top by 1.

You need to check if the stack is empty before popping and the opposite for pushing.

Pseudo Code - Infinite Size

Push(S,x)
top++
S[top] = x

Pop(S)
if top == 0 then
	stack is EMPTY
else 
begin
	x = S[top]
	top--
	return x
end

Pseudo Code - Limited Size

Push(S,x)
if top == size then
	stack is FULL
else
begin
	top++
	S[top] = x
end

Post-fix Expressions with Stacks

You can use the stack to compute mathematical operations. This is the case if you use reverse Polish notation. This style of notation makes the precedence implicit.

Method

  1. Rad the next token from the expressions which may be operator or operand.
  2. If token is operand, PUSH it to stack.
  3. If token is operator;
    • POP two operand from stack.
    • Operate on the two operands.
    • PUSH result back to stack.
  4. If expression is not exhausted, go back to step 1.
  5. If expression is exhausted, evaluation finished and answer is on top of stack.
Example

Evaluate 10 3 2 * - 5 *

Expression Stack
10 3 2 * - 5 *  
3 2 * - 5 * 10
2 * - 5 * 10, 3
* - 5 * 10 , 3, 2
- 5 * 10, 6 - Push top two, complete operand, push result.
5 * 4 - Push top two, complete operand, push result.
* 4, 5
  20 - Push top two, complete operand, push result.

Convert Infix to Postfix Expression Using Stack

Whenever an operator is popped, output it.

  1. Read the next token from the expression which may be operator, operand, ( or ).
    • If token is operand, OUTPUT it.
    • If token is (, PUSH it on the stack.
    • If token is ), POP from the stack until matching (.
    • If token is operator, POP from stack until you see one of the following:
      • An operator with same/lower precedence.
      • An opening (.
      • The stack is empty.
    • PUSH the operator on stack.
  2. If expression is not exhausted, go to step 1.
  3. If expression is exhausted, POP rest of stack.