Tutorial 3

📚

Stack

9618 A-Level

i

Note: for AS, the syllabus states you won't be asked to write a stack from scratch - but they do have "fill in the blank" type questions where they give you most of the code and ask you to complete it

For A2, you can be asked to write an entire stack from scratch, including the push and pop modules

It may be useful to search (CTRL + F) for "stack" questions in the (combined) past papers

If you find any bugs/edge cases in this code, please contact me

1

Stack

A stack is a LIFO (last-in, first-out) data structure - there are two operations and we will require an additional pointer variable that points to the top element in the stack

  1. Push: if the stack isn't full, a new item will be added to the top of the stack and the top pointer will be incremented
  2. Pop: if the stack isn't empty, the top item will be removed and returned from the stack and the top pointer will be decremented

More detailed comments can be seen in the code

//declarations CONSTANT STACK_SIZE ← 3 DECLARE Top : INTEGER DECLARE Stack : ARRAY[1:STACK_SIZE] OF STRING //testing CALL ResetStack() CALL Push("a") CALL Push("b") CALL Push("c") CALL Push("d") CALL OutputStack() OUTPUT "Popping elements..." OUTPUT Pop() OUTPUT Pop() OUTPUT Pop() OUTPUT Pop() CALL OutputStack() //main stack implementation PROCEDURE ResetStack() Top ← 0 //don't need to clear elements, only need to reset top pointer since pushing new elements will overwrite existing dat ENDPROCEDURE PROCEDURE Push(Item : CHAR) //check stack isn't full IF Top < STACK_SIZE THEN Top ← Top + 1 Stack[Top] ← Item //push item to top position OUTPUT "Pushed ", Item, " at index ", Top ELSE OUTPUT "Stack is full - can't push ", Item ENDIF ENDPROCEDURE FUNCTION Pop() RETURNS STRING IF Top > 0 THEN DECLARE Item : STRING Item ← Stack[Top] //get item at top of stack Top ← Top - 1 RETURN Item ELSE OUTPUT "Error - nothing to pop" RETURN "" ENDIF ENDFUNCTION PROCEDURE OutputStack() OUTPUT "--- Stack Contents ---" //loop through from top to bottom of stack FOR pos ← Top TO 1 STEP -1 OUTPUT pos, ": ", Stack[pos] NEXT pos OUTPUT "----------------------" ENDPROCEDURE

Extension details/answers will be added: reverse a string, check balanced brackets, evaluate postfix expression