[问答] 请用任意语言实现数据结构中的栈

[android-cn]

[问答] 请用任意语言实现数据结构中的栈

[yummmyz]

java语言版本：

class Stack{
LinkedList list;//声明集合

/**
 * 无参构造方法
 */
public Stack(){
    list=new LinkedList();//创建集合
}

/**
 * 添加方法
 * @param o
 */
public void add(Object o){
    list.push(o);//将元素添加进集合第一个元素 
}

/**
 * 获取方法
 * @return
 */
public Object get(){
    return list.pop();//删除集合的首元素并返回
}

/**
 * 获取集合长度
 * @return
 */
public int size(){
    return list.size();
}

}

[R1NC]

虽然说的是 “任意语言”，但面试官考察的就是：

• 怎么建数据结构;
• push() 和 pop() 等操作的实现；

所以，直接用 built-in 的集合类 API 肯定是不行的。

对于栈，主要是理解其 “单向操作”、“先进后出” 的特性。

这里给出 Golang 版本的实现（链式存储），不熟悉 Golang 也没关系（其实跟 C 语言很像），**是一样的，我下面注释也很详细：

package stack

//定义节点数据结构(仅供内部使用):
type node struct {
    value interface{} //节点数据(任意类型);
    next *node //下一个节点的指针;
}

//定义链栈数据结构(供外部使用):
type LinkedStack struct {
    top *node //栈顶指针;
    size int //栈大小;
}

//读取栈大小:
func (stack *LinkedStack) Size() int {
    return stack.size //直接返回size变量的值;
}

//入栈操作:
func (stack *LinkedStack) Push(value interface{}) {
    new_node := &node{value, stack.top} //创建新的栈顶节点，其next指针指向原栈顶指针;用临时指针变量保存其地址;
    stack.top = new_node //修改栈顶指针，指向新节点;
    new_node = nil //销毁临时指针变量(注意这里不能清空new_node.value和new_node.next，因为通过new_node实际操作的是整个栈顶节点!);
    stack.size++ //修改栈大小;
}

//出栈操作(删除栈顶节点):
func (stack *LinkedStack) Pop() {
    if stack.size == 0 { //判断栈是否为空;
        panic("Stack is empty.")
    }
    top_node := stack.top //临时保存原来的栈顶结点指针(用于后面的销毁操作);
    stack.top = top_node.next //修改栈顶结点为当前栈顶结点的next指针;
    top_node.value = nil //销毁原来的栈顶结点(注意这三步的顺序：先清数据，再将next指针置为空，最后将该指针置为空。顺序错了会导致空指针操作异常);
    top_node.next = nil
    top_node = nil
    stack.size-- //修改栈大小;
}

//读取栈顶节点数据(不删除该节点):
func (stack *LinkedStack) Peek() interface{} {
    if stack.size == 0 { //判断栈是否为空;
        panic("Stack is empty.")
    }
    return stack.top.value //返回栈顶节点的数据;
}

测试代码：

package stack

import (
    "fmt"
    "testing"
)

func Test_linked_stack(t *testing.T) {
    stack := &LinkedStack{}
    stack.Push("iOS")
    stack.Push("Android")
    stack.Push("WindowsPhone")
    stack.Push("Symbian")
    stack.Push("BalckBerry")
    for stack.Size() > 0 {
        fmt.Printf("%s\n", stack.Peek())
        stack.Pop()
    }
}

注意

• 上面的 Push() 函数我使用 new_node 临时指针变量是为了增强代码可读性，其实可以一步到位：

func (stack *LinkedStack) Push(value interface{}) {
    stack.top = &node{value, stack.top}
    stack.size++
}

• Pop() 函数也可以直接返回栈顶节点数据（不需要 Peek() 操作）。这个看具体需求了，代码稍作修改即可：

func (stack *LinkedStack) Pop() interface{} {
    if stack.size == 0 {
        panic("Stack is empty.")
    }
    top_node := stack.top
    stack.top = top_node.next
    x := top_node.value //保存原栈顶元素数据(用于返回);
    top_node.value = nil
    top_node.next = nil
    top_node = nil
    stack.size--
    return x //返回原栈顶元素数据;
}

基本数据结构与算法的 Golang 实现

[yanbober]

mark