ALGORITHM SERIES | Use One Stack To Sort Another Stack
Overview
Requirements
A stack whose elements are of type integer now wants to sort the stack from top to bottom in order from smallest to largest, and only one stack is allowed to be requested. Other than that, new variables can be requested, but no additional data structures can be requested. How to complete the sorting?
Solution
- apply for a new help stack, keep getting data from the original stack, and compare it with the top data of the new help stack; if it meets the sorting requirements, then push it to the help stack
- if it does not meet the sorting requirements, pop the top data from the help stack and push it to the original stack until it meets the sorting requirements
- Finally, the original stack is emptied, and the help stack is the stack that is all sorted, so write it back again to complete the stack sorting.
Golang Implementation
1package main
2
3// SortStark stark top --> stark bottom(from small to big)
4func SortStark(stk *Stack) {
5 helpStack := NewStack()
6 // 1. while go through target stack until stack is empty
7 for stk.Len() > 0 {
8 cur := stk.Pop()
9 // 2. if cur < peek, push helpStack.pop() to target stack until cur > peek or helpStack is empty
10 for (helpStack.Len() > 0) && (cur.(int) < helpStack.Peek().(int)) {
11 stk.Push(helpStack.Pop())
12 }
13 // 3. if helkStack is not empty, compare cur with helpStack's peek value
14 // 4. while cur > peek, push cur to helpStack
15 helpStack.Push(cur)
16 }
17 // 5. push back helpStack to target stack
18 for helpStack.Len() > 0 {
19 stk.Push(helpStack.Pop())
20 }
21}
Test Cases
1package main
2
3import (
4 "testing"
5
6 "github.com/stretchr/testify/assert"
7)
8
9func TestSortStark(t *testing.T) {
10 tests := []struct {
11 name string
12
13 val *Stack
14
15 wantRes []int
16 }{
17 {
18 name: "sortstark",
19 val: NewStack(),
20 // transpose once, then return to the original order of last-in first-out
21 wantRes: []int{0, 1, 2, 3, 5, 8},
22 },
23 }
24 for _, tt := range tests {
25 t.Run(tt.name, func(t *testing.T) {
26 // test case
27 stk := tt.val
28 stk.Push(2)
29 stk.Push(8)
30 stk.Push(1)
31 stk.Push(5)
32 stk.Push(0)
33 stk.Push(3)
34 SortStark(stk)
35 res := []int{}
36 for stk.length > 0 {
37 res = append(res, tt.val.Pop().(int))
38 }
39 assert.Equal(t, tt.wantRes, res)
40 })
41 }
42}
Result:
1$ go test -run ^TestSortStark$ . -v
2=== RUN TestSortStark
3=== RUN TestSortStark/sortstark
4--- PASS: TestSortStark (0.00s)
5 --- PASS: TestSortStark/sortstark (0.00s)
6PASS
7
8Process finished with the exit code 0
Tested with no problems and successfully completed sorting.