p. 407 · PDF 417

1 - 3 Stack and Queue

Stack and queue are data structures that model the methods of using data. They are also called problem resolution data structures, and they are implemented by using an array.

1-3-1 Stack

Stack is an LIFO (Last-In First-Out) data structure where data that is recorded last is extracted first. You can simply imagine a data structure where data is stacked in the box, and data is extracted from the box. Since data is stacked and extracted from the same side, data that is stored most recently is extracted first. Storing data in the stack is called PUSH, and extracting data from the stack is called POP. · 4 questions

p. 408 · PDF 418

Enlarge original visual

Original source text

Figure 7-5  Image of stack 

Source visual description

The original stack drawing shows PUSH and POP operations and the changing Data 1 and Data 2 contents.

For implementing a stack, it is a common practice to use an SP (Stack Pointer). The stack pointer shows the position (i.e., index if an array structure) of the topmost element of the stack at present. When data is stored, data is recorded in the position where the value of the stack pointer is updated (e.g., generally +1). In contrast, when data is extracted, the value of the stack pointer is updated (e.g., generally −1) after data is extracted from the position of the stack pointer. For ease of understanding, the process of storing (i.e., pushing) data is shown in the figure below. Here, an array in the figure is shown as reversed. · 2 questions

Enlarge original visual

Source visual description

Original Stack and Queue source layout. Source labels: .

A stack is suitable for temporarily storing return address or data that is being processed during a function call or a recursive call. In addition, OS and application programs use stacks after stack space is secured in main memory.